#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdbool.h>

struct ListNode {
    int val;
    struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head) {

    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* cur = head;
    struct ListNode* phead = NULL;
    while (cur) {
        struct ListNode* next = cur->next;
        cur->next = phead;
        phead = cur;
        cur = next;

    }
    return phead;
}

bool chkPalindrome(struct ListNode* A) {
    // write code here
    struct ListNode* mid = middleNode(A);
    struct ListNode* rhead = reverseList(mid);
    while (A && rhead)
    {
        if (rhead->val != A->val)
            return false;
        rhead = rhead->next;
        A = A->next;
    }
    return true;
}